package solutions.leetcode.hard

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/">1671. 得到山形数组的最少删除次数</a>
 */
private class Solution1671 {
    /*

    1   0,0
    3   0,1
    2   1,2
    6   1,3
    5   2,4

    2   0+1+1+1+1 -> 4+1
    1   2+1+1+1+1
    5   2+1+1+1
    6   2+1+1
    3   4
    0,1,2,2,2,4,4,7
    6,6,5,2,1,1,0,0
    2,1,1,5,6,2,3,1

     */
    data class Data(val count: Int, val ind: Int)

    fun minimumMountainRemovals(nums: IntArray): Int {
        val map = HashMap<Int, Data>()
        val count = IntArray(nums.size)
        for ((ind, item) in nums.withIndex()) {
            count[ind] += findMin(map, item, ind)
        }
        nums.reverse()
        map.clear()
        for ((ind, item) in nums.withIndex()) {
            count[nums.size - 1 - ind] += findMin(map, item, ind)
        }
        var t = count[1]
        for (i in 1 until nums.size - 1) {
            t = Math.min(count[i], t)
        }
        return t
    }

    fun findMin(map: HashMap<Int, Data>, item: Int, ind: Int): Int {
        val below = map.filter { it.key < item }

        val c = if (below.isEmpty()) ind else {
            var t = Int.MAX_VALUE
            for (bi in below) {
                t = Math.min(t, bi.value.count + ind - 1 - bi.value.ind)
            }
            t
        }
        map[item] = Data(c, ind)
        return if (below.isEmpty()) 1001 else c
    }
}

fun main() {
    println(
        Solution1671().minimumMountainRemovals(
            arrayOf(
                100,92,89,77,74,66,64,66,64
            ).toIntArray()
        )
    )
}